package com.lei.tree.traversal;


import java.util.*;

public class TraversalDemo {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public void preOrder(TreeNode root, ArrayList<Integer> list){
        if(root == null){
            return ;
        }
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);
    }
    public void inOrder(TreeNode root, ArrayList<Integer> list){
        if(root == null){
            return ;
        }
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right,list);
    }
    public void postOrder(TreeNode root, ArrayList<Integer> list){
        if(root == null){
            return ;
        }
        postOrder(root.left,list);
        postOrder(root.right,list);
        list.add(root.val);
    }
    public ArrayList<Integer> preOrderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        preOrder(root, result);
        return result;
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        inOrder(root,res);
        return res;
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        postOrder(root, res);
        return res;
    }
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        TraversalDemo traversalDemo = new TraversalDemo();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        System.out.println(Arrays.asList(traversalDemo.preOrderTraversal(root)));
        System.out.println("*********************");
        System.out.println(Arrays.asList(traversalDemo.inorderTraversal(root)));
        System.out.println("*********************");
        System.out.println(Arrays.asList(traversalDemo.postorderTraversal(root)));

    }

}
